package medium;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2021/8/31 19:54
 */
public class No29_两数相除 {
    public static void main(String[] args) {
        Solution29 solution29 = new Solution29();
        int dividend = 1;
        int divisor = 2;
        int res = solution29.divide(dividend, divisor);
        System.out.println(res);
    }
}

class Solution29 {
    public int divide(int dividend, int divisor) {
        //边界条件
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }
        if (dividend == 0) {
            return 0;
        }
        //不用乘法、除法和 mod 运算符 计算结果
        //1.sign,代表结果的符号
        int sign = 1;
        //2.全转负计算(规避计算过程中溢出问题)
        if (dividend > 0) {
            dividend = -dividend;
        } else {
            sign = -sign;
        } 
        
        if (divisor > 0) {
            divisor = -divisor;
        } else {
            sign = -sign;
        }
        int q = 0;
        //获取数:原始的除数
        int yuan = divisor;
        int preDivisor = divisor;
        int res = 0;
        while (true) {
            divisor = yuan;
            // 扩大过后,过头!! 变正,什么原因?? 左移过头了....
            //大坑!!!!!!!!!!!!!!!!!
            while (dividend <= divisor && divisor < 0) {
                //2
                if (divisor == yuan) {
                    q = 1;
                } else {
                    q = q << 1;
                } 
                //扩大之前保存
                preDivisor = divisor;
                //扩大,扩大过头变正,bug!!!!坑
                divisor = divisor << 1; //-4272
            }
            res += q;
            dividend = dividend - preDivisor;
            if (dividend > yuan) {
                break;
            }
            
        }
        if (sign == -1) {
            return -res;
        }
        return res;
    }
}




